//34 在排序区间中查找给定元素的第一个和最后一个位置
/*
给定一个增序的整数数组和一个值，查找该值第一次和最后一次出现的位置

输入输出样例：
	输入是一个数组和一个值，输出为该值第一次出现的位置和最后一次出现的位置（从 0 开
始）；如果不存在该值，则两个返回值都设为-1

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

*/
// 主函数
vector<int> searchRange(vector<int> &nums, int target)
{
	if (nums.empty())
		return vector<int>{-1, -1};
	int lower = lower_bound(nums, target);
	int upper = upper_bound(nums, target) - 1; // 这里需要减1位
	if (lower == nums.size() || nums[lower] != target)
	{
		return vector<int>{-1, -1};
	}
	return vector<int>{lower, upper};
}
// 辅函数
int lower_bound(vector<int> &nums, int target)
{
	int l = 0, r = nums.size(), mid;
	while (l < r)
	{
		mid = (l + r) / 2;
		if (nums[mid] >= target)
		{
			r = mid;
		}
		else
		{
			l = mid + 1;
		}
	}
	return l;
}
// 辅函数
int upper_bound(vector<int> &nums, int target)
{
	int l = 0, r = nums.size(), mid;
	while (l < r)
	{
		mid = (l + r) / 2;
		if (nums[mid] > target)
		{
			r = mid;
		}
		else
		{
			l = mid + 1;
		}
	}
	return l;
}